package backtrack

func partition(s string) [][]string {
	res := make([][]string, 0)
	path := make([]string, 0)
	var dfs func(index int)
	dfs = func(index int) {
		if index >= len(s) {
			tmp := make([]string, len(path))
			copy(tmp, path)
			res = append(res, tmp)
		}
		for i := index; i < len(s); i++ {
			if isPalindrome(s, index, i) {
				curr := s[index: i + 1]
				path = append(path, curr)
			} else {
				continue
			}
			dfs(i + 1)
			path = path[:len(path) - 1]
		}
	}
	dfs(0)
	return res
}

func isPalindrome(s string, start, end int) bool {
	for i, j := start, end; i < j; i++ {
		if s[i] != s[j] {
			return false
		}
		j--
	}
	return true
}